import copy
class Solution(object):
    def backtrace(self, nums, depth, path, res, used):
        if len(nums) == depth:
            res.append(copy.deepcopy(path))
            return

        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                self.backtrace(nums, depth+1, path, res, used)
                used[i] = False
                path.pop()

    def permute(self, nums):
        used = [False for _ in range(len(nums))]
        res = []
        self.backtrace(nums, 0, [], res, used)
        return res

